package algorithms.a05binarysearchtree;

import com.google.common.base.Preconditions;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二分搜索树
 * 由于Key需要能够进行比较，所以需要extends Comparable<Key>
 *
 * @author 王昊然
 * @create 2018-02-17 22:46
 **/
public class BST<Key extends Comparable<Key>, Value> {


    private Node root;  // 根节点
    private int count;  // 树种的节点个数

    // 构造函数, 默认构造一棵空二分搜索树
    public BST() {
        root = null;
        count = 0;
    }

    // 返回二分搜索树的节点个数
    public int size() {
        return count;
    }

    // 返回二分搜索树是否为空
    public boolean isEmpty() {
        return count == 0;
    }

    public void insert(Key key, Value value) {
        Preconditions.checkNotNull(key, "插入的key值不允许为空！");
        root = insert(root, key, value);
    }

    /**
     * 递归方法，在node中插入新的键值对
     *
     * @param node  待执行插入键值对的node
     * @param key
     * @param value
     * @return 执行完插入或更新键值对的node
     * @date: 2018/2/17 23:20
     * @author: 王昊然
     */
    private Node insert(Node node, Key key, Value value) {

        if (node == null) {
            count++;
            return new Node(key, value);//结束递归条件1 插入新node
        } else if (key.equals(node.key)) {
            node.value = value; //结束递归条件2 更新node

        } else if (key.compareTo(node.key) < 0) {
            node.left = insert(node.left, key, value);
        } else {//key.compareTo(node.key) > 0
            node.right = insert(node.right, key, value);
        }

        return node;
    }

    /**
     * 不用递归的插入方法
     * 老师github并无相关代码，纯自己实现的
     *
     * @param key
     * @param value
     */
    public void insertNoRecursive(Key key, Value value) {

        Preconditions.checkNotNull(key, "插入的key值不允许为空！");

        if (root == null) {
            count++;
            root = new Node(key, value);
        } else if (key.equals(root.key)) {
            root.value = value; //更新node
        }

        Node parent = root;
        int leftOrRight = 0;//0是left 1是right；

        while (true) {
            Node child = null;
            if (key.compareTo(parent.key) < 0) {
                child = parent.left;
                leftOrRight = 0;
            } else if (key.compareTo(parent.key) > 0) {//key.compareTo(node.key) > 0
                child = parent.right;
                leftOrRight = 1;
            }

            if (child == null) {
                if (leftOrRight == 0) {
                    parent.left = new Node(key, value);
                } else {
                    parent.right = new Node(key, value);
                }
                count++;
                break;
            } else if (key.equals(child.key)) {
                child.value = value; //更新node
                break;
            }
            //key != child.key
            parent = child;
        }
    }

    public Value search(Key key) {
        if (key == null) {
            Preconditions.checkNotNull(key, "查找的key不可为空");
        }

        return search(root, key);
    }

    private Value search(Node node, Key key) {

        if (node == null) {
            return null;
        } else if (key.equals(node.key)) {
            return node.value;
        } else if (key.compareTo(node.key) < 0) {
            return search(node.left, key);
        } else {
            return search(node.right, key);
        }
    }


    public boolean contain(Key key) {
        if (key == null) {
            Preconditions.checkNotNull(key, "查找的key不可为空");
        }

        return contain(root, key);
    }

    private boolean contain(Node node, Key key) {

        if (node == null) {
            return false;
        } else if (key.equals(node.key)) {
            return true;
        } else if (key.compareTo(node.key) < 0) {
            return contain(node.left, key);
        } else {
            return contain(node.right, key);
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {

        if (node != null) {
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }

    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }

    public void leverOrder() {

        if (root == null) return;

        List<Node> nodeList = new LinkedList<>();//用list作为队列
        nodeList.add(root);

        while (!nodeList.isEmpty()) {
            Node node = nodeList.remove(0);
            System.out.println(node.value);

            if (node.left != null) {
                nodeList.add(node.left);
            }
            if (node.right != null) {
                nodeList.add(node.right);
            }
        }
    }

    /**
     * 在树中找最小节点
     *
     * @return
     */
    public Node minimum() {
        if (root == null) return root;
        return minimum(root);
    }

    private Node minimum(Node node) {

        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 在树中找最大节点
     *
     * @return
     */
    public Node maximum() {
        if (root == null) return root;
        return maximum(root);
    }

    private Node maximum(Node node) {

        if (node.right == null) {
            return node;
        }
        return maximum(node.left);
    }

    /**
     * 删除树的最小值
     *
     * @return 被删除的节点
     */
    public void removeMin() {
        if (root == null) return;
        root = removeMin(root);
    }

    /**
     * 删除node对应子树的最小节点
     *
     * @param node
     * @return 删除node后的子树根节点
     */
    private Node removeMin(Node node) {

        if (node.left == null)
            return node.right;

        node.left = removeMin(node.left);

        return node;
    }

    /**
     * 删除树的最大值
     *
     * @return 被删除的节点
     */
    public void removeMax() {
        if (root == null) return;
        root = removeMax(root);
    }

    /**
     * 删除node对应子树的最大节点
     *
     * @param node
     * @return 删除node后的子树根节点
     */
    private Node removeMax(Node node) {

        if (node.right == null)
            return node.left;

        node.right = removeMax(node.right);

        return node;
    }

    public void remove(Key key) {
        root = remove(root, key);

    }

    /**
     * 递归删除子树中key的节点
     *
     * @param node
     * @param key
     * @date: 2018/2/22 9:54
     * @author: 王昊然
     */
    private Node remove(Node node, Key key) {
        if (node == null) return null;

        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            return node;
        } else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            return node;
        }

        //node.key == key;
        if(node.left == null){
            return node.right;
        }else if(node.right == null){
            return node.left;
        }

        //node.left !=null &&  node.right !=null;
        /*
            hubbard deletion：将node与右子树的最小key节点交换
         */
        Node minright = minimum(node.right);
        minright.left = node.left;
        minright.right = removeMin(node.right);

        return minright;

    }


    // 树中的节点为私有的类, 外界不需要了解二分搜索树节点的具体实现
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
}



